package demo.practice.dp;

public class P198 {

    //动态规划  典型题
    public int rob(int[] nums) {
        //dp数组记录 打劫到的总金额
        //dp[i] 代表打劫 了  打劫完第i家店 所得的总金额

        //1、  在第i家打劫的时候有两种情况
        // 第i家打劫，则第i-1家是不能打劫的 。金额为i-2打劫到的总金额 加上 当前这家打劫到的金额    dp[i]= dp[i-2]+ nums[i]
        // 第i家不打劫  则第i-1家是可以打劫的  那么 此时打劫到的总金额  就是打劫到i-1家时的总金额：  dp[i]= dp[i-1]

        //打劫完第0家打劫的金额为 nums[0]  ：dp[0]=nums[0]
        //打劫完第1家的打劫的金额为 第0家和第1家中 金额更大的（肯定两者选更大的金额打劫）    dp[0]= Math.max(nums[0],nums[1])
        if(nums==null|| nums.length==0)
            return -1;

        if (nums.length == 1) {
            return nums[0];
        }



        int[] dp = new int[nums.length];

        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);

        for(int i=2;i<nums.length;i++ ){
            dp[i]= Math.max(dp[i-1],dp[i-2]+ nums[i] );
        }

        return dp[dp.length-1];
    }
}
